#include "outline/guided_poly_bezier_builder.h"
#include "outline/bezier_guide.h"
#include <limits>

namespace outline {

template <typename T, typename R>
void guided_poly_bezier_builder<T, R>::clear()
{
	clear_nodes();
	areas_.clear();
	all_estimations_.clear();
}

template <typename T, typename R>
void guided_poly_bezier_builder<T, R>::reset(nodes_type const & polyline, 
	area_cptr_vector_type const & areas, std::vector<junc_type> const & junc)
{
	reset_nodes(polyline);
	assert(!areas.empty());
	areas_ = areas;
	assert(areas.size() == junc.size());
	junc_ = junc;
	all_estimations_.clear();
}

template <typename T, typename R>
void guided_poly_bezier_builder<T, R>::set_params(params_type const & params)
{
	params_ = params;
}

template <typename T, typename R>
void guided_poly_bezier_builder<T, R>::inspect_all_pieces()
{
	if (!all_estimations_.empty())
		return;
	uint acount = areas_.size();
	all_estimations_.resize(acount);
	for (uint i = 0; i < acount; ++i) {
		uint i1 = (i+1) % acount;
		area_type const & a = *areas_[i];
		uint ncount = a.size();
		assert (ncount > 0);
		area_type const & a1 = *areas_[i1];
		uint n1count = a1.size();
		assert (n1count > 0);
		estimation_image_type & eimage = all_estimations_[i];
		eimage.resize(ncount, n1count);
		for (uint k = 0; k < ncount; ++k) 
		{
			uint begin = a[k];

			incremental_bezier_guide<T,R> ibg;
			ibg.max_iterations = params_.low_max_iterations;
			ibg.stop_mean_discrepancy = params_.low_stop_mean_discrepancy;
			ibg.oversample_factor = params_.low_oversample_factor;

			for (uint l = 0; l < n1count; ++l) 
			{
				if (acount == 1) {
					assert(ncount == n1count);
					if (l != k) {
						eimage(k, l).null();
						continue;
					}
				}
				uint end = a1[l];
				if (end <= begin)
					end += size_;
				assert (begin < end);
				uint len = end - begin + 1;
				if (len < 4)
					eimage(k, l).null();
				else {
					R e = ibg.fit(nodes_, begin, end+1);
					assert (e >= 0);
					eimage(k, l) = estimation_type(e, ibg.b.start_d(), ibg.b.finish_d());
				}
			}
		}
	}
}

template <typename T, typename R>
R guided_poly_bezier_builder<T, R>::select_best(index_vector_type & ivec)
{
	uint acount = areas_.size();

	if (!params_.low) {
		//junctions the centers of areas
		ivec.resize(acount + 1);
		for (uint j = 0; j < acount; ++j) {
			area_type const & a = *areas_[j];
			ivec[j] = a[a.size()/2];
			if (j != 0 && ivec[j] < ivec[j-1])
				ivec[j] += size_;
		}
		ivec[acount] = ivec[0] + size_;
		return 0;
	}

	if (all_estimations_.empty())
		return -1;

	ivec.clear();
	real_type best_D = std::numeric_limits<R>::max();
	uint best_start;

	if (acount == 1) {
		assert(junc_[0] == junc_cusp);
		area_type const & a = *areas_[0];
		estimation_image_type const & estimations0 = all_estimations_[0];
		uint fcount = area_size(acount-1); //the number of possible routes' starts and finishes in zero's area
		for (uint k = 0; k < fcount; ++k) {
			estimation_type const & e = estimations0(k, k);
			if (e.is_null())
				continue;
			real_type d = e.d;
			if (params_.sharpness_penalty > 0)
				d += sharpness_penalty(params_.sharpness_penalty, e.d2, e.d1);
			if (d < best_D) {
				best_D = d;
				best_start = k;
			}
		}
		if (best_D == std::numeric_limits<R>::max())
			return -1;
		ivec.push_back(a[best_start]);
		ivec.push_back(a[best_start] + size_);
		return best_D;
	}

	nexts_type nexts;
	estimation_image_type routes;
	select_best_open_core(nexts, routes);
	uint best_finish;

	estimation_image_type const & estimationsx = all_estimations_[acount - 1];
	assert (routes.width() == estimationsx.height());
	assert (estimationsx.width() == routes.height());
	estimation_image_type::const_iterator it;
	for (it = estimationsx.begin(); it != estimationsx.end(); ++it) {
		if ((*it).is_null()) //missing element in open route
			continue;
		estimation_type const & route = routes(it.y(), it.x());
		if (route.is_null())
			continue;
		real_type d = (*it).d + route.d;
		if (params_.sharpness_penalty > 0) {
			if (junc_[0] != junc_cusp)
				d += sharpness_penalty(params_.sharpness_penalty, route.d1, (*it).d2);
			if (junc_[acount - 1] != junc_cusp)
				d += sharpness_penalty(params_.sharpness_penalty, route.d2, (*it).d1);
		}
		if (d < best_D) {
			best_D = d;
			best_start = it.y();
			best_finish = it.x();
		}
	}

	if (best_D == std::numeric_limits<R>::max())
		return -1;

	ivec.reserve(acount + 1);
	ivec.push_back((*areas_[0])[best_start]);
	uint j = best_start;
	for (uint anum = 0; anum+1 < acount; ++anum) {
		j = nexts[anum](j, best_finish);
		ivec.push_back((*areas_[anum+1])[j]);
	}
	assert (j == best_finish);
	ivec.push_back((*areas_[0])[best_start]);

	//make ivec monotonically increasing
	for (j = 1; j < ivec.size(); ++j) {
		uint & prev = ivec[j - 1];
		uint & curr = ivec[j];
		if (curr < prev)
			curr += size_;
		assert (curr > prev);
	}

	return best_D;
}

template <typename T, typename R>
typename guided_poly_bezier_builder<T,R>::estimation_type const & 
guided_poly_bezier_builder<T,R>::get_estimation(uint begin, uint len, uint piece_num) const
{
	uint acount = areas_.size();
	assert (piece_num < acount);

	area_type const & a = *areas_[piece_num];
	uint ncount = a.size();
	uint k;
	for (k = 0; k < ncount; ++k) {
		if (a[k] == begin)
			break;
	}
	assert (k != ncount);

	area_type const & a1 = *areas_[(piece_num + 1) % areas_.size()];
	uint n1count = a1.size();
	uint l;
	for (l = 0; l < n1count; ++l) {
		if (a1[l] == (begin + len - 1) % size_)
			break;
	}
	assert (l != n1count);

	return all_estimations_[piece_num](k, l);
}

template <typename T, typename R>
void guided_poly_bezier_builder<T,R>::select_best_open_core(nexts_type & nexts, 
	estimation_image_type & routes)
{
	uint acount = areas_.size();
	assert (acount > 1);
	uint fcount = area_size(acount-1); //the number of possible routes' finishes
	nexts.resize(acount - 1);

	//build routes from the pre-last area to the last area
	uint heada = acount - 2;
	uint necka = acount - 1;
	next_image_type & im = nexts[heada];
	routes.attach(all_estimations_[heada]);
	assert (routes.height() == fcount);
	im.resize(routes.dim());
	next_image_type::iterator it;
	for (it = im.begin(); it != im.end(); ++it)
		*it = it.y();

	if (acount == 2)
		return;

	//build longer routes
	do {
		estimation_image_type subroutes;
		subroutes.swap(routes);
		--heada;
		--necka;
		estimation_image_type const & head_estimations = all_estimations_[heada];
		routes.clear();
		routes.resize(area_size(heada), fcount);
		next_image_type & im = nexts[heada];
		im.resize(routes.dim());
		uint m_max = area_size(necka);
		for (it = im.begin(); it != im.end(); ++it) {
			estimation_type & route = routes[it];
			route.null();
			for (uint m = 0; m < m_max; ++m) {
				estimation_type const & heade = head_estimations(it.x(), m);
				if (heade.is_null())
					continue;
				estimation_type const & necke = subroutes(m, it.y());
				if (necke.is_null())
					continue;
				real_type d = heade.d + necke.d;
				if (params_.sharpness_penalty > 0 && junc_[necka] != junc_cusp)
					d += sharpness_penalty(params_.sharpness_penalty, heade.d2, necke.d1);
				if (route.is_null() || route.d > d) {
					route.d = d;
					route.d1 = heade.d1;
					route.d2 = necke.d2;
					*it = m;
				}
			}
		}
	} while (heada != 0);
}

template <typename T, typename R>
void guided_poly_bezier_builder<T,R>::get_junction_types(
	index_vector_type const & ivec, std::vector<junc_type> & junc) const
{
	//uint jcount = smooth_junctions.size();
	//assert(ivec.size() == jcount + 1);
	junc = junc_;
}

template guided_poly_bezier_builder<unsigned short>;
template guided_poly_bezier_builder<short>;
template guided_poly_bezier_builder<int>;
template guided_poly_bezier_builder<float>;
template guided_poly_bezier_builder<double>;

} //namespace outline
